import operator
import random
import defaultvalue
import randommove
import searchalg

##################################################
# class used in A* algorithm
##################################################
class Node: # each grid's structure
    def __init__(self, node_pos, flag = 1):
        self.leaf_flag = flag # the root node?
        self.color = defaultvalue.WHITE # not been vistied
        self.reachable = False
        self.x = node_pos[0]
        self.y = node_pos[1]
        self.G = 0
        self.H = 0
        self.F = 0
        
    def init_nodes(self, parent, destination, corner = False):
        self.set_route(parent)
        if corner == False: # move catercorner?
            self.G = self.parent.G + defaultvalue.span
        self.H = (operator.abs(destination[0] - self.x) + operator.abs(destination[1] - self.y))\
                 * defaultvalue.span # Manhattan Distance
        self.F = self.G + self.H

    def set_color(self, color):
        """ set whether a grid's visited status """
        self.color = color

    def set_reachable(self, reachable):
        self.reachable = reachable

    def set_route(self, parent):
        """ last grid """
        self.parent = parent        

    def __lt__(self, vertex1):
        """ use < to compare two grids """
        return self.F < vertex1.F

class CHeap: # the heap structure
    def __init__(self):
        self.nodelist = [] # save the nodes
        self.length = 0

    def parent(self, i):
        return i/2 # get the grid's index ,return another index

    def left(self, i):
        return i * 2

    def right(self, i):
        return i * 2 + 1

    def exchange(self, i ,j):
        temp = self.nodelist[i - 1]
        self.nodelist[i - 1] = self.nodelist[j - 1]
        self.nodelist[j - 1] = temp
        
    def min_heap(self,i):
        """ maitain a heap's property """
        l = self.left(i)
        r = self.right(i)
        minimum = i
        if l <= len(self.nodelist) and self.nodelist[l - 1] < self.nodelist[i - 1]:
            minimum = l
        if r <= len(self.nodelist) and self.nodelist[r - 1] < self.nodelist[minimum - 1]:
            minimum = r
        if minimum != i:
            self.exchange(i, minimum) # put the minimum among the parent and the two sons to the top
            self.min_heap(minimum)

    def add_node(self, nodes):
        """ add node to the heap """
        self.nodelist.append(nodes)        
        self.length += 1
        index = self.length
        # move the node until his parent is less than him
        while index > 1 and self.nodelist[self.parent(index) - 1] > self.nodelist[index - 1]:
            self.exchange(index, self.parent(index))
            index = self.parent(index)

    def get_min(self):
        if self.length < 1: # list is empty
            raise 'Exception','heap underflow'
        minnodes = self.nodelist.pop(0)
        self.length -= 1
        self.min_heap(1) # maintain the heap's property
        return minnodes

##################################################
# A* algorithm
##################################################
class AStar(searchalg.SearchAlg):
    def __init__(self):
        self.reset()

    def reset(self):
        self.map = []
        self.reachFlag = 0 # whether the destination is reached
        self.blocked = 0 # whether the destination is blocked
        self.dic = {} # save all the nodes that have ever been visited
        self.heap = CHeap() # sava the nodes being dealed with
        self.way = [] # the route

    def add_nodes(self, nodes):
        """ visit a new grib """
        nodes.set_color(defaultvalue.GRAY) # visiting a grid, but have not finished visiting his alley gribs 
        self.dic.update({nodes.x * self.length + nodes.y : nodes}) # key is Manhattan Distance, value is himself
        self.heap.add_node(nodes)

    def judge_nodes(self, nodes):
        """ a new grib ? """
        index = nodes.x * self.length + nodes.y # dic's key
        if self.dic.has_key(index) == False: # haven't visited
            return True
        else: # have visted the grib
            temp_node = self.dic.get(index)
            if temp_node.F > nodes.F and temp_node.color != defaultvalue.BLACK: # have not finish visting
                temp_node.F = nodes.F # a route with less distance
                temp_node.set_route(nodes.parent)
            return False

    def add_adj(self, nodes):
        """ add neighbor gribs """
        flag = random.randint(0 , 3) # randomize the sequence that the neighbors join in the heap 
        index = 0 # the num of neighbors that have been visited
        while index < 4:
            index += 1
            # up grid
            if flag == 0:
                flag = (flag + 1) % 4
                pos = [nodes.x - 1, nodes.y]
                if pos[0] >= 0 and self.map[pos[0]][pos[1]] == 0: # the position exist and has not been occupied
                    temp_node = Node(pos)
                    if temp_node.leaf_flag : # not root node, so save its parent
                        temp_node.init_nodes(nodes, self.destination)
                    if self.judge_nodes(temp_node): # have not been visted?
                        self.add_nodes(temp_node)
            # left grid
            if flag == 1:
                flag = (flag + 1) % 4
                pos = [nodes.x , nodes.y - 1]
                if pos[1] >= 0 and self.map[pos[0]][pos[1]] == 0:
                    temp_node = Node(pos)
                    if temp_node.leaf_flag :
                        temp_node.init_nodes(nodes, self.destination)
                    if self.judge_nodes(temp_node):
                        self.add_nodes(temp_node)            
            # down grid
            if flag == 2:
                flag = (flag + 1) % 4
                pos = [nodes.x + 1 , nodes.y ]
                if pos[0] < self.length and self.map[pos[0]][pos[1]] == 0:
                    temp_node = Node(pos)
                    if temp_node.leaf_flag :
                        temp_node.init_nodes(nodes, self.destination)
                    if self.judge_nodes(temp_node):
                        self.add_nodes(temp_node)
            # right grid
            if flag == 3:
                flag = (flag + 1) % 4
                pos = [nodes.x , nodes.y + 1]
                if pos[1] < self.height and self.map[pos[0]][pos[1]] == 0:
                    temp_node = Node(pos)
                    if temp_node.leaf_flag :
                        temp_node.init_nodes(nodes, self.destination)
                    if self.judge_nodes(temp_node):
                        self.add_nodes(temp_node)
    
    def calculate(self):
        """ salculate the shortest route """
        tree_root = Node(self.start_position, 0) # the start position is the root
        self.add_nodes(tree_root)
        while self.heap.length > 0: # visit all the gribs that are reachable from the root
            temp_node = self.heap.get_min()
            self.lastgrid = temp_node
            self.add_adj(temp_node)
            temp_node.set_color(defaultvalue.BLACK) # finish visiting this grib and its neighbors
            index = self.destination[0] * self.length + self.destination[1] # the destination's key
            if self.dic.has_key(index) and self.dic.get(index).color == defaultvalue.BLACK:
                self.reachFlag = 1 # finish visiting the destination and its neighbors
                break          

    def search_route(self):
        if self.reachFlag == 1:
            sNode = self.dic.get(self.start_position[0] * self.length + self.start_position[1])
            dNode = self.dic.get(self.destination[0] * self.length + self.destination[1])
            self.get_route(sNode, dNode)
        else: # the destination is not reachable, so move to the last  visited grid instead
            sNode = self.dic.get(self.start_position[0] * self.length + self.start_position[1])
            dNode = self.lastgrid
            self.get_route(sNode, dNode)

    def get_route(self, s , v):
        """ recursion, get the route """
        if v == s:
           pass
        else:
            self.get_route(s, v.parent) # along its parent
            if v.parent.x == v.x - 1 and v.parent.y == v.y :
                self.way.append(2) # down
            if v.parent.x == v.x  and v.parent.y == v.y - 1:
                self.way.append(3) # right
            if v.parent.x == v.x + 1 and v.parent.y == v.y :
                self.way.append(0) # up
            if v.parent.x == v.x  and v.parent.y == v.y + 1:
                self.way.append(1) # left

    def search(self, map, start_position, end_position):
        """ init the algorithm, and find a route """
        self.reset()
        self.map = map
        self.length = len(map)
        self.height = len(map[0])
        self.start_position = start_position
        self.destination = end_position
        i = self.destination[0]
        j = self.destination[1]
        # test if the destination is not reachable. If so, random move
        status = [1, 1, 1, 1]
        if i - 1 >= 0 and self.map[i - 1][j] == 0:
            status[0] = 0
        if j - 1 >= 0 and self.map[i][j - 1] == 0:
            status[1] = 0
        if i + 1 < self.length and self.map[i+1][j] == 0:
            status[2] = 0
        if j + 1 < self.height and self.map[i][j + 1] == 0:
            status[3] = 0
        self.blocked = status[0] & status[1] & status[2] & status[3]
        if self.blocked:
            move_al = randommove.RandomMove()
            self.way = move_al.search(self.map, self.start_position, self.destination)
        else:
            self.calculate()
            self.search_route()
        return self.way
   